import java.util.Arrays;

public class MaxSum {
    /**
     * 最大子数组和
     * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     *
     */
    public static int maxS(int[] nums){
        // 动态规划
        int ans=Integer.MIN_VALUE;
        int[] dp=new int[nums.length];

        // 初始化
        dp[0]=nums[0];
        ans=dp[0];
        for(int i=1;i< nums.length;i++){
            dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
            ans=Math.max(ans,dp[i]);
        }
        return ans;
    }

    /**
     * 找到最大和的第一个子段的元素的起始位置和结束位置
     *
     */
    public static int[] maxSubArray(int[] nums){
        int []res=new int[3];
        int start=0,end=0;
        int maxSum=nums[0],curSum=nums[0];
        for(int i=1;i< nums.length;i++){
            if(curSum+nums[i]<nums[i]){
                curSum=nums[i];
                start=i;
            }else {
                curSum+=nums[i];
            }

            if(curSum>maxSum){
                maxSum=curSum;
                end=i;
            }
        }

        res[0]=maxSum;
        res[1]=start;
        res[2]=end;

        return res;
    }

    public static void main(String[] args) {
        int []nums={-2,1,-3,4,-1,2,1,-5,4};

        System.out.println(Arrays.toString(nums));
        System.out.println(maxS(nums));

        System.out.println(Arrays.toString(maxSubArray(nums)));
    }
}
